package leetcode.code1553;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;
//执行用时：3 ms, 在所有 Java 提交中击败了95.60%的用户
//
//内存消耗：40.6 MB, 在所有 Java 提交中击败了22.64%的用户
//
//通过测试用例：176 / 176
public class Solution2 implements IDebug {

	Map<Integer, Integer> map = new HashMap<>();

	public int minDays(int n) {
		Map<Integer, Integer> hash = new HashMap<>();
		this.f(n, hash);
		for (Entry entry : map.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}
		return 0;
	}

	private int f(int n, Map<Integer, Integer> hash) {
		if (n <= 1) {
			return n;
		}
		if (hash.containsKey(n)) {
			return hash.get(n);
		}
		map.put(n, map.getOrDefault(n, 0) + 1);
		int ans1 = n % 2 + 1 + this.f(n / 2, hash);
		int ans2 = n % 3 + 1 + this.f(n / 3, hash);
		int ans = Math.min(ans1, ans2);
		hash.put(n, ans);
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(4, this.minDays(10));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(32, this.minDays(2000000000));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
